教学相长和寓教于乐的两个故事

这些年，在上本科生的一门课“社会科学中的计算思维方法”，同时也不时地以“社会科学中的计算思维浅赏”为题，给其他学校作些讲座。学生和听众的表现经常给我带来惊喜。因此，本文标题中的“乐”其实不是给了学生，而主要是于我本人而言了，这也算是对那名句含义的曲解吧。

一个例子是关于匹配市场均衡价格的性质。问题是这样定义的：给定n×n矩阵V，其中元素按惯例记为v_ij，要求得一组称为“清仓价格”的值p=(p₁, p₂, …, p_n)，和一个[n]上的映射，满足对所有i=1, 2, …, n，

（1）

上课的时候不宜上来就是这么一个定义，用一个具体例子往往更加有效。如图1所示，右边是一个3×3矩阵（V），左边则是一组价格（p）。中间放上了一个二部图（称为“偏好卖家图”），其中的边对应在给定价格下的“最大差价”，也就是上面的公式（1），而其中3条较粗的边，对应的就是映射关系。这样的映射关系也称为二部图的一个完美匹配。

可以想象，一般地给定V，要找到这样一组p不是件容易的事，同时，也可能想象，这样的p也不一定是唯一的，如(5, 2, 0)就是另一组。在我们的课上，一般也就讲到这里，然后是介绍一个利用“物以稀为贵”的观念保证能求出一组清仓价格p的算法。

拓展一些，会提到学术文献中关于清仓价格集合的一个性质（凸性），即若p和q是清仓价格，那么λp+(1-λ)q也是清仓价格，其中λ在0和1之间。就上面的例子而言，取p=(3,1,0)，q=(5,2,0)，λ=0.2，有0.2×3+0.8×5=4.6，0.2×1+0.8×2=1.8，即(4.6,1.8,0)也是一组清仓价格（有兴趣的读者可以检验一下）。关于这个性质的证明，一般教材都没有，我想大概是因为其要求的背景知识比较多。为此特别咨询了这个领域的专家邓小铁教授，问他“哪里能找到比较通俗的证明？”他答：“约束条件是凸的。两个最优解的效用函数是相等的。目标函数是线性的。所以，两个最优解的凸组合满足约束条件，与最优解等值。即得。”

精辟！但这段话要有多深厚的积累才能理解啊。

这时候，本故事的主人公出场了，选修本学期课程的林涛同学说可以提供一个初等证明。下面就来看他的证明。

引理：设p=(p₁, p₂, …, p_n)和q=(q₁, q₂, …, q_n)为两个清仓价格向量。记A和B为分别由p和q引起的完美匹配集合（即符合要求的s的集合），则A=B。

证明：用G(p)和G(q)表示对应p和q的偏好卖家图（即图1中间的那种二部图）。

考虑G(p)中任一完美匹配M={（i₁,j₁），（i₂,j₂），…，（i_n,j_n）}。我们将通过证明M中的每一条边也在G(q)中，来说明M也是G(q)中的一个完美匹配。

假设（i₁, j₁）不在G(q)中。因q是清仓价格，于是至少有一个完美匹配N在G(_q)中。由于假设（i₁, j₁）不在G(q)中，i₁在N中一定与某个其他的j匹配，不失一般性，设i₁和j₂匹配；这样，i₂也就没有和j₂匹配，设它与j₃匹配……直到某一个k，i_k与j₁匹配；也就是（i₁, j₂），（i₂, j₃），…，（i_k, j₁）∈N。

考虑（i₁, j₁）和i₁, j₂）。因为（i₁, j₁）是M中的一条边，按清仓价格的定义，有v_i1j1-p_j1≥v_i1j2-p_j2，而因为（i₁, j₂）是N中的一条边且（i₁, j₁）不是N中的，就有v_i1j1-q_j1<v_i1j2-q_j2。将上述两个不等式相减，得

类似考虑其他的边，就有

……

把它们相加，就得到矛盾的0<0。这个矛盾说明前面“假设（i₁, j₁）不在G(q)中”是不成立的。于是，p的任一完美匹配的所有边都在G(q)中，即为q的一个完美匹配。对称地，q的每一个完美匹配也都是p的完美匹配。证毕。

现在我们可以看为什么r=λp+(1-λ)q也是清仓价格了。由引理，p和q有共同的完美匹配N。假设i在N中与j匹配，对任何k≠j，有

分别乘以系数λ和（1-l）就是

和

相加得

即对于任何k≠j 

这就是说r是一组清仓价格。至此，就完成了关于清仓价格凸性的一个初等证明。

我没有查到是否前面有人给出过这个证明。鉴于清仓价格概念在匹配市场问题中的核心地位，以及林涛这个证明的优雅，我以为它是可以放到未来的面向非数学专业的本科生教材中的。这样一个证明，完全不需要有凸优化知识，只需要了解匹配市场模型，有初等数学程度上的成熟和较好的逻辑思维能力，就可以理解。

第二个故事与最近在一所独立学院的几个讲座有关。我一直认为“社会科学中的计算思维”是一个广谱的话题，应该让更多的学子有所接触，且相信年轻人都能在一定程度上体会和理解，也许就能影响他们今后的职业生涯和对生活的态度。

这次安排的是一个系列讲座的形式，对学生们来说算16个课时合1个学分。讲课过程中，总有一些两眼放光能跟上我节奏的学生。第一次课后我布置了几个习题，其中包括要计算下面这个网络节点的Pagerank，并且我给了参考答案（即可以通过计算得到的均衡值）：0, 1/3, 1/3, 1/3（如图2所示）。

第二次课上，有学生站起来质疑，说按照课上介绍的Pagerank算法，得不到我给的这个结果，除了A=0，其他3个节点的值是在1/2, 1/4, 1/4之间轮转。更进一步地，他说查资料了，要用一种称为“阻尼”的方法才能使迭代收敛（只是还没明白那种方法是什么，希望能知道）。

这一方面让我大喜——孺子可教！另一方面让我有些为难——不太可能在那种场合把话题展开。更重要的是，当时我虽然能猜到他说的“阻尼”是怎么回事，但对Pagerank的收敛性，我还没有用自己的语言归纳出一种完整的说法。于是我告诉他，课后给我发邮件，我一定回复。

后来那学生真的给我发邮件了，而我呢，回来后把与Pagerank的收敛性相关的问题认真梳理了一遍，得到结论如下：

从教学的角度，总是先讲Pagerank基本算法（单纯用“入向节点的值/度数”之和作更新，在我的讲座中只是提到了这个基本算法），然后根据需要讲缩减与补偿算法（即那个同学说的“阻尼”方法，其中用到一个参数s∈(0,1)）。

由佩龙定理（关于正矩阵的结论）保证，缩减与补偿算法总是收敛的，且结果唯一（与初值无关）。

基本算法的情况就要复杂许多。虽然在Pagerank意义下的均衡值总是存在的（佩龙定理关于非负矩阵的结论），但取决于网络结构，可能收敛，也可能不收敛。收敛结果可能与初值无关，也可能与初值有关。例如，图3（1）总是收敛的，但收敛结果与初值有关；另一方面，如果网络图是强连通的，虽然也不保证收敛，但是若收敛则是唯一的。图3（2）就是一个例子，它一般来说不收敛，但若收敛，结果就是1/4，1/4，1/4，1/4。

进而，我们可以估计到，如果一个网络结构和初值设定在基本算法下不会收敛，则在缩减与补偿算法下收敛的速度与s有关，越大收敛得越慢。

可以说，Pagerank是这些年可以用“风靡”来形容的一个概念，许多场合都用到过，熟悉的读者也一定不少。在这里，也希望与其他老师探讨，我上面的说法是否还有漏洞？

类似这样的故事，在过去这些年的教学过程中经历不少，几乎每学期都有。讲课的内容能引起学生的思考，他们的反馈也让我有所提高，实为快哉。例如这一次在该独立学院，整个课程讲完之后做了一个问卷，其中一个问题是：

你认为在本校是否应该开这种内容的课程：

184个学生提交的结果如图4所示。

这个问卷结果让我很受鼓舞。前面也提到，上课的时候总能看到一些两眼放光跟上我节奏的学生。当然，也不可避免地有一些低头族，而且有学生向他们的老师反馈说我布置的作业太难，不会做，提交上来的作业基本就是我给的参考答案，但这个问卷结果很说明问题，代表了大多数同学的支持态度，而那些反馈问题的情况也属于“正常范围”。同时，这个问卷结果也再一次支持了这样一个信念：爱学习是年轻人的特质，问题可能在于学什么和怎么学，同时也延伸出一个学习环境怎样以及怎样教的问题。

基金项目：自然科学基金项目（NSFC61632017）。

参考文献：

[1]Nisan N, Roughgarden T, Tardos E, et al. Algorithmic game theory[M]. Cambridge: Cambridge University Press, 2007: 103-158. 

[2]大卫•伊斯利, 乔恩•克莱因伯格. 网络、群体与市场[M]. 李晓明, 王卫红, 杨韫利, 译. 北京: 清华大学出版社, 2018: 175-190. 

扩展阅读：北大李晓明教授：为什么会有“数据结构”？

（完）

更多精彩：